#include "main/utils.h"
using namespace std;

int genRandomByProbility(const vector<int> &weight) {
  vector<int> sum_weight;
  int sum = 0;
  for (int i = 0; i < weight.size(); ++i) {
    sum += weight[i];
    sum_weight.push_back(sum);
  }

  int rand_num = rand() % sum;
  int begin = 0;
  int end = sum_weight.size() - 1;
  while (begin <= end) {
    int mid = (begin + end) / 2;
    if (sum_weight[mid] > rand_num) {
      if (mid == 0 || sum_weight[mid - 1] <= rand_num) {
        return mid;
      }
      end = mid - 1;
    } else {
      begin = mid + 1;
    }
  }
  return -1;
}

int main() {
  vector<int> weight = {1, 2, 3, 4};
  cout << genRandomByProbility(weight) << endl;
  cout << genRandomByProbility(weight) << endl;
  cout << genRandomByProbility(weight) << endl;
  cout << genRandomByProbility(weight) << endl;
  cout << genRandomByProbility(weight) << endl;
  cout << genRandomByProbility(weight) << endl;
  cout << genRandomByProbility(weight) << endl;
  cout << genRandomByProbility(weight) << endl;
  cout << genRandomByProbility(weight) << endl;
  cout << genRandomByProbility(weight) << endl;

  return 0;
}
